<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 找城市（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>一张地图上有n个城市&#xff0c;城市和城市之间有且只有一条道路相连&#xff1a;要么直接相连&#xff0c;要么通过其它城市中转相连&#xff08;可中转一次或多次&#xff09;。城市与城市之间的道路<strong>都不会成环</strong>。</p> 
<p>当切断通往某个城市 i 的所有道路后&#xff0c;地图上将分为多个连通的城市群&#xff0c;设该城市i的聚集度为DPi&#xff08;Degree of Polymerization&#xff09;&#xff0c;DPi &#61; max&#xff08;城市群1的城市个数&#xff0c;城市群2的城市个数&#xff0c;…城市群m 的城市个数&#xff09;。</p> 
<p>请找出地图上DP值最小的城市&#xff08;即找到城市j&#xff0c;使得DPj &#61; min(DP1,DP2 … DPn))</p> 
<p>提示&#xff1a;如果有<strong>多个城市</strong>都满足条件&#xff0c;这些城市都要找出来&#xff08;<strong>可能存在多个解</strong>&#xff09;</p> 
<p>提示&#xff1a;DPi的计算&#xff0c;可以理解为已知一棵树&#xff0c;删除某个节点后&#xff1b;生成的多个子树&#xff0c;求解多个子数节点数的问题。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>每个样例&#xff1a;第一行有一个整数N&#xff0c;表示有N个节点。1 &lt;&#61; N &lt;&#61; 1000。</p> 
<p>接下来的N-1行每行有两个整数x&#xff0c;y&#xff0c;表示城市x与城市y连接。1 &lt;&#61; x,  y &lt;&#61; N</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出城市的编号。如果有多个&#xff0c;按照编号升序输出。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">5<br /> 1 2<br /> 2 3<br /> 3 4<br /> 4 5</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>输入表示的是如下地图&#xff1a;</p> <p><img alt="" height="235" src="https://img-blog.csdnimg.cn/88d239f2968b4ef5849bc054163f34ea.png" width="704" /></p> <p>对于城市3&#xff0c;切断通往3的所有道路后&#xff0c;形成2个城市群[&#xff08;1&#xff0c;2&#xff09;&#xff0c;&#xff08;4&#xff0c;5&#xff09;]&#xff0c;其聚集度分别都是2。DP3 &#61; 2。</p> <p>对于城市4&#xff0c;切断通往城市4的所有道路后&#xff0c;形成2个城市群[&#xff08;1&#xff0c;2&#xff0c;3&#xff09;&#xff0c;&#xff08;5&#xff09;]&#xff0c;DP4 &#61; max&#xff08;3&#xff0c;1&#xff09;&#61; 3。</p> <p>依次类推&#xff0c;切断其它城市的所有道路后&#xff0c;得到的DP都会大于2&#xff0c;因为城市3就是满足条件的城市&#xff0c;输出是3。</p> </td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">6<br /> 1 2<br /> 2 3<br /> 2 4<br /> 3 5<br /> 3 6</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2 3</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">将通往2或者3的所有路径切断&#xff0c;最大城市群数量是3&#xff0c;其他任意城市切断后&#xff0c;最大城市群数量都比3大&#xff0c;所以输出2 3</td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>用例1的意思如下&#xff1a;</p> 
<p>DPi &#61; max&#xff08;城市群1的城市个数&#xff0c;城市群2的城市个数&#xff0c;…城市群m 的城市个数&#xff09;</p> 
<p><img alt="" height="703" src="https://img-blog.csdnimg.cn/0c381ed4a9cf42e5ac6bb22a079330b8.png" width="449" /></p> 
<p> 题目要求找出地图上DP值最小的城市&#xff08;即找到城市j&#xff0c;使得DPj &#61; min(DP1,DP2 … DPn))&#xff0c;</p> 
<p>因此DP3最小&#xff0c;输出DP3的3。</p> 
<p></p> 
<p>用例2图示如下</p> 
<p><img alt="" height="311" src="https://img-blog.csdnimg.cn/f220cb5b6209401da3467da058606b22.png" width="378" /></p> 
<p><img alt="" height="302" src="https://img-blog.csdnimg.cn/b0b6efdb52dc4a468d490e5c4acac5fc.png" width="1200" /></p> 
<p>输出2&#xff0c;3。</p> 
<p></p> 
<p>通过上面两个示例的图示可以发现&#xff0c;其实本题就是求解&#xff1a;图的连通分量。</p> 
<p>本题的难点在于&#xff0c;分量关系没有直接给出&#xff0c;需要我们自己推导&#xff0c;其次是需要我们统计出每个连通分量的节点个数。</p> 
<p><img alt="" height="330" src="https://img-blog.csdnimg.cn/61a62018ee1343ec9d1eff0d336e74ff.png" width="368" /></p> 
<p>比如&#xff0c;上面且1的所有联系&#xff0c;则会产生两个连通分量&#xff0c;分别是[1], [4,2,3,5,6]&#xff0c;这两个连通分量的节点个数分别为1&#xff0c;5。</p> 
<p></p> 
<p>求解图的连通分量&#xff0c;我们一般使用并查集。</p> 
<p>但是&#xff0c;这里我们不能直接根据输入的连接关系&#xff0c;来产生并查集&#xff0c;因为输入的连接关系没有被切断。</p> 
<p>本题是要我们尝试切断每一个城市的连接&#xff0c;因此我们遍历出每一个城市&#xff0c;比如城市2&#xff0c;然后遇到和城市2相关的连接后&#xff0c;我们就跳过并查集的合并操作&#xff0c;这样就能产生切断效果。</p> 
<p></p> 
<p>我们模拟下用例2</p> 
<p>初始时&#xff0c;每个城市的父都是自己</p> 
<p><img alt="" height="118" src="https://img-blog.csdnimg.cn/ee145a81f85e425ca201fbb0149edcd0.png" width="363" /></p> 
<p>输入的连接关系如下<br /> 1 2<br /> 2 3<br /> 2 4<br /> 3 5<br /> 3 6</p> 
<p>现在我们要切断城市2的所有联系&#xff0c;则遇到和2相关的连接时就不进行合并操作</p> 
<p>因此上述连接关系只需要考虑<br /> 3 5<br /> 3 6</p> 
<p>这样的话&#xff0c;最终并查集的合并结果为</p> 
<p><img alt="" height="114" src="https://img-blog.csdnimg.cn/e28ba981324540b18d73b82332b4f265.png" width="346" /></p> 
<p><img alt="" height="317" src="https://img-blog.csdnimg.cn/f0916f03ac9546d2b2a8ed2fc6f73ddb.png" width="361" /></p> 
<p>可以发现&#xff0c;父为3的连通分量具有最多城市数量</p> 
<p></p> 
<p>这样的话&#xff0c;我们就可以求解出每个DPi了&#xff0c;最后求其中最小的DP对应i即可。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81" style="background-color:transparent;">JavaScript算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const n &#61; parseInt(await readline());

  const relations &#61; [];
  for (let i &#61; 0; i &lt; n - 1; i&#43;&#43;) {
    relations.push((await readline()).split(&#34; &#34;).map(Number));
  }

  console.log(getMinDP(relations, n));
})();

function getMinDP(relations, n) {
  // minDp用于保存最小城市聚集度
  let minDp &#61; Infinity;
  // city用于保存最小城市聚集度对应的被切割的城市序号
  let city &#61; [];

  // 遍历每个城市 1~n
  for (let i &#61; 1; i &lt;&#61; n; i&#43;&#43;) {
    // 利用并查集对城市进行关联
    const ufs &#61; new UnionFindSet(n &#43; 1);

    for (let [x, y] of relations) {
      // 切断城市的所有道路&#xff0c;即忽略和城市i有联系的合并操作
      if (x &#61;&#61;&#61; i || y &#61;&#61;&#61; i) continue;
      // 否则连接x和y
      ufs.union(x, y);
    }

    // 统计各个连通分量自身的城市个数
    const cnts &#61; new Array(n &#43; 1).fill(0);
    for (let j &#61; 1; j &lt;&#61; n; j&#43;&#43;) {
      const fa &#61; ufs.find(j);
      cnts[fa]&#43;&#43;;
    }

    // 取最多城市个数作为当前的切断城市的聚集度
    const dp &#61; Math.max(...cnts);

    if (dp &lt; minDp) {
      minDp &#61; dp;
      city &#61; [i];
    } else if (dp &#61;&#61;&#61; minDp) {
      city.push(i);
    }
  }

  // 如果有多个&#xff0c;按照编号升序输出。
  city.sort((a, b) &#61;&gt; a - b);
  return city.join(&#34; &#34;);
}

/* 并查集 */
class UnionFindSet {
  constructor(n) {
    this.fa &#61; new Array(n).fill(0).map((_, idx) &#61;&gt; idx);
  }

  find(x) {
    if (x !&#61;&#61; this.fa[x]) {
      return (this.fa[x] &#61; this.find(this.fa[x]));
    }
    return x;
  }

  union(x, y) {
    let x_fa &#61; this.find(x);
    let y_fa &#61; this.find(y);

    if (x_fa !&#61;&#61; y_fa) {
      this.fa[y_fa] &#61; x_fa;
    }
  }
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    int n &#61; sc.nextInt();

    int[][] relations &#61; new int[n - 1][2];
    for (int i &#61; 0; i &lt; n - 1; i&#43;&#43;) {
      relations[i][0] &#61; sc.nextInt();
      relations[i][1] &#61; sc.nextInt();
    }

    System.out.println(getResult(n, relations));
  }

  public static String getResult(int n, int[][] relations) {
    // 记录最小dpi
    int minDp &#61; Integer.MAX_VALUE;
    // 记录最小dpi对应的切断城市
    ArrayList&lt;Integer&gt; city &#61; new ArrayList&lt;&gt;();

    // i 是被切断城市
    for (int i &#61; 1; i &lt;&#61; n; i&#43;&#43;) {
      // 利用并查集对城市进行关联
      UnionFindSet ufs &#61; new UnionFindSet(n &#43; 1);

      for (int[] relation : relations) {
        int x &#61; relation[0];
        int y &#61; relation[1];
        // 如果x或y是被切断城市&#xff0c;则对应连接关系不成立
        if (x &#61;&#61; i || y &#61;&#61; i) continue;
        // 否则连接x和y
        ufs.union(x, y);
      }

      int[] cnts &#61; new int[n &#43; 1];
      for (int j &#61; 1; j &lt;&#61; n; j&#43;&#43;) {
        // 对j&#61;1~n每个城市找根fa
        int fa &#61; ufs.find(j);
        // 根fa下的子城市个数&#43;&#43;
        cnts[fa]&#43;&#43;;
      }

      // cnts的最大值即最大城市群大小
      int dp &#61; Arrays.stream(cnts).max().orElse(0);

      // 和minDp比较&#xff0c;保留最小值
      if (dp &lt; minDp) {
        minDp &#61; dp;
        city &#61; new ArrayList&lt;&gt;();
        city.add(i);
      } else if (dp &#61;&#61; minDp) {
        city.add(i);
      }
    }

    // 如果有多个&#xff0c;按照编号升序输出。
    city.sort((a, b) -&gt; a - b);
    StringJoiner sj &#61; new StringJoiner(&#34; &#34;);
    for (Integer c : city) {
      sj.add(c &#43; &#34;&#34;);
    }
    return sj.toString();
  }
}

// 并查集实现
class UnionFindSet {
  int[] fa;

  public UnionFindSet(int n) {
    this.fa &#61; new int[n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) fa[i] &#61; i;
  }

  public int find(int x) {
    if (this.fa[x] !&#61; x) {
      return this.fa[x] &#61; this.find(this.fa[x]);
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa &#61; this.find(x);
    int y_fa &#61; this.find(y);

    if (x_fa !&#61; y_fa) {
      this.fa[y_fa] &#61; x_fa;
    }
  }
}
</code></pre> 
<p></p> 
<h4 style="background-color:transparent;">Python算法源码</h4> 
<pre><code class="language-python">import sys

# 输入获取
n &#61; int(input())
relations &#61; [list(map(int, input().split())) for i in range(n - 1)]


# 并查集
class UnionFindSet:
    def __init__(self, n):
        self.fa &#61; [i for i in range(n)]

    def find(self, x):
        if x !&#61; self.fa[x]:
            self.fa[x] &#61; self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa &#61; self.find(x)
        y_fa &#61; self.find(y)
        if x_fa !&#61; y_fa:
            self.fa[y_fa] &#61; x_fa


# 算法入口
def getResult():
    # minDp用于保存最小城市聚集度
    minDp &#61; sys.maxsize
    # city用于保存最小城市聚集度对应的被切割的城市序号
    city &#61; []

    # 遍历每个城市 1~n
    for i in range(1, n &#43; 1):
        # 利用并查集对城市进行关联
        ufs &#61; UnionFindSet(n &#43; 1)

        for x, y in relations:
            # 切断城市的所有道路&#xff0c;即忽略和城市i有联系的合并操作
            if x &#61;&#61; i or y &#61;&#61; i:
                continue
            # 否则连接x和y
            ufs.union(x, y)

        # 统计各个连通分量自身的城市个数
        cnts &#61; [0] * (n &#43; 1)
        for j in range(1, n &#43; 1):
            fa &#61; ufs.find(j)
            cnts[fa] &#43;&#61; 1

        #  取最多城市个数作为当前的切断城市的聚集度
        dp &#61; max(cnts)

        if dp &lt; minDp:
            minDp &#61; dp
            city &#61; [i]
        elif dp &#61;&#61; minDp:
            city.append(i)

    # 如果有多个&#xff0c;按照编号升序输出。
    city.sort()
    return &#34; &#34;.join(map(str, city))


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4 style="background-color:transparent;">C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;limits.h&gt;

/** 并查集定义 **/
typedef struct {
    int *fa;
} UFS;

UFS *new_UFS(int n) {
    UFS *ufs &#61; (UFS *) malloc(sizeof(UFS));

    ufs-&gt;fa &#61; (int *) malloc(sizeof(int) * n);
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
        ufs-&gt;fa[i] &#61; i;
    }

    return ufs;
}

int find_UFS(UFS *ufs, int x) {
    if (x !&#61; ufs-&gt;fa[x]) {
        ufs-&gt;fa[x] &#61; find_UFS(ufs, ufs-&gt;fa[x]);
        return ufs-&gt;fa[x];
    }
    return x;
}

void union_UFS(UFS *ufs, int x, int y) {
    int x_fa &#61; find_UFS(ufs, x);
    int y_fa &#61; find_UFS(ufs, y);

    if (x_fa !&#61; y_fa) {
        ufs-&gt;fa[y_fa] &#61; x_fa;
    }
}

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}

/**   算法入口   **/
int main() {
    int n;
    scanf(&#34;%d&#34;, &amp;n);

    int relations[n - 1][2];
    for (int i &#61; 0; i &lt; n - 1; i&#43;&#43;) {
        scanf(&#34;%d %d&#34;, &amp;relations[i][0], &amp;relations[i][1]);
    }

    // 记录最小dpi
    int minDp &#61; INT_MAX;

    // 记录最小dpi对应的切断城市
    int city[n];
    int city_size &#61; 0;

    // i 是被切断城市
    for (int i &#61; 1; i &lt;&#61; n; i&#43;&#43;) {
        // 利用并查集对城市进行关联
        UFS *ufs &#61; new_UFS(n &#43; 1);

        for (int j &#61; 0; j &lt; n - 1; j&#43;&#43;) {
            int x &#61; relations[j][0];
            int y &#61; relations[j][1];

            // 如果x或y是被切断城市&#xff0c;则对应连接关系不成立
            if (x &#61;&#61; i || y &#61;&#61; i) continue;

            // 否则连接x和y
            union_UFS(ufs, x, y);
        }

        // cnts记录每个根&#xff08;每个节点都能当成一个根来看&#xff09;下的城市个数
        int cnts[n &#43; 1];
        for (int k &#61; 0; k &lt;&#61; n; k&#43;&#43;) {
            cnts[k] &#61; 0;
        }

        for (int k &#61; 1; k &lt;&#61; n; k&#43;&#43;) {
            // 对k&#61;1~n每个城市找根fa
            int fa &#61; find_UFS(ufs, k);
            // 根fa下的子城市个数&#43;&#43;
            cnts[fa]&#43;&#43;;
        }

        // cnts的最大值即最大城市群大小
        int dp &#61; cnts[1];
        for (int k &#61; 2; k &lt;&#61; n; k&#43;&#43;) {
            if (cnts[k] &gt; dp) {
                dp &#61; cnts[k];
            }
        }

        // 和minDp比较&#xff0c;保留最小值
        if (dp &lt; minDp) {
            minDp &#61; dp;
            city_size &#61; 0;
            city[city_size&#43;&#43;] &#61; i;
        } else if (dp &#61;&#61; minDp) {
            city[city_size&#43;&#43;] &#61; i;
        }
    }

    // 如果有多个&#xff0c;按照编号升序输出。
    qsort(city, city_size, sizeof(int), cmp);

    for (int i &#61; 0; i &lt; city_size; i&#43;&#43;) {
        printf(&#34;%d&#34;, city[i]);
        if (i !&#61; city_size - 1) {
            printf(&#34; &#34;);
        }
    }

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>